//
// Created by dgy on 2022/11/10.
//


#include "iostream"
#include "vector"
#include "queue"
#include "stack"
using namespace std;
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> b;
        if (root==NULL)
            return b;
        queue<TreeNode*> queue;
        queue.push(root);
        int flag=1;
        while (!queue.empty()){
            vector<int> tmp;
            int size=queue.size();
            if(flag==-1){
                for(;size--;queue.pop()){
                    TreeNode* p=queue.front();
                    if (p->left)
                        queue.push(p->left);
                    if (p->right)
                        queue.push(p->right);
                    tmp.push_back(p->val);
                }
            }else{
                for(;size--;queue.pop()){
                    TreeNode* p=queue.front();
                    if (p->right)
                        queue.push(p->right);
                    if (p->left)
                        queue.push(p->left);
                    tmp.push_back(p->val);
                }
            }
            flag*=-1;
            b.push_back(tmp);
        }
        return b;
    }
};